The subject invention relates to a method and apparatus for performing multiplication and/or modular reduction computations. The subject method and apparatus can utilize the Barrett modular reduction algorithm (see for example Menezes, A., van Oorschot, P., and Vanstone, S., Handbook of Applied Cryptography, CRC Press, 1996) to implement automatic computing machinery. The subject method and apparatus can be used to implement modular multiplication and exponentiation operations.
In the past, it has often been impractical to implement large-scale digital processors using a single semiconductor device due to the limitations of the amount of logic that can be placed on such a device. This has led to the selection and development of processors that are optimized for minimum silicon resource utilization. Modular reduction and modular multiplication has been implemented using the Montgomery reduction or Montgomery multiplication algorithms (see for example Menezes, et al.). Implementations using the Montgomery algorithms have the advantage of requiring less memory and fewer discreet multiplication operations than required to implement the Barrett algorithm. As it became possible to integrate large-scale digital processors onto a single semiconductor device, the methodology of using Montgomery algorithm implementations was carried forward. An example of such a digital processor is given in U.S. Pat. No. 6,085,210 (Buer). Other examples of Montgomery algorithm digital processors can be found in U.S. Pat. No. 6,240,436 (McGregor), U.S. Pat. No. 6,282,290 (Powell, et al.), and U.S. Pat. No. 6,185,596 (Hadad, et al.). These implementations suffer from limitations in the ability to exploit and sustain parallel use of many multipliers, thus limiting their overall processing speed.
The Barrett modular reduction algorithm is given here to establish notation (see for example Menezes, et al.).
Let x be a non-negative integer with up to a 2k digit radix b representation (x={x2k−1, . . . , x1, x0}). Let m be a modulus with a k digit radix b representation where the most significant digit is not equal to zero (m={mk−1, . . . , m1, m0}, mk−1≠0). The Barrett modular reduction algorithm computes r=x mod m, where r∈{0, 1, 2, . . . , m−1}. Define μ=└b2k/m┘. The algorithm is given by the following steps.    1. q1←└x/bk−1┘, q2←q1μ, q3←└q2/bk+1┘    2. r1←x mod bk+1, r2←q3m mod bk+1, r←r1−r2     3. If r<0 then r←r+bk+1     4. While r≧m do: r←r−mNote that it is well-known that step 4 in the above algorithm will repeat not more than twice.
For an implementation of the Barrett algorithm using digital logic it is preferable to choose the radix b to be a power of two (e.g., b=232). Given the radix is a power of two, define N to be the number of bits per radix b digit; that is, N=log2 b. It should be noted that if b is a power of two then the operator └•/bk┘ is a right shift by k N-bit digits, and the operator (• mod bk) is the k least significant N-bit digits.